#include "stdafx.h"
#include "graph.h"

using namespace std;


const int iIle = 2;
const double dIle = 2.0;
ofstream out1_m, out1_l, out2_m, out2_l;
clock_t tstart, tstop;
double ttime;
double avg, sum;

CGraph * graf_m, * graf_l;
int ** matrix;

void help() {

        cout << "Use: sdizo.exe <nr_algorytmu> <nr_testu>\n";
        cout << "\tZapis np w pliku: 'd_m_1.txt' (Dijkstra, macierzowa, pierwszy test)\n";
        cout << "Nr_algorytmu:\n\t1: Dijkstra(d) i Bellmana-Forda(b)\n\t2: Kruskala(k) i Prima(p)\n";

}

void Dijkstra( int v ) {

        for( int i=0; i<v; ++i )
                for( int j=i+1; j<v; ++j )
                        if( matrix[ i ][ j ] != 0 ) {
                                graf_m->AddDirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                                graf_l->AddDirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                        }

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_m->Dijkstra( 1 );
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out1_m << avg << endl;

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_l->Dijkstra( 1 );
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out1_l << avg << endl;
}
void BellmanFord( int v ) {

        for( int i=0; i<v; ++i )
                for( int j=i+1; j<v; ++j )
                        if( matrix[ i ][ j ] != 0 ) {
                                graf_m->AddDirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                                graf_l->AddDirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                        }

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_m->BellmanFord( 1 );
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out2_m << avg << endl;

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_l->BellmanFord( 1 );
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out2_l << avg << endl;
}
void Kruskal( int v ) {

        for( int i=0; i<v; ++i )
                for( int j=i+1; j<v; ++j )
                        if( matrix[ i ][ j ] != 0 ) {
                                graf_m->AddUndirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                                graf_l->AddUndirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                        }

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_m->Kruskal();
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out1_m << avg << endl;

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_l->Kruskal();
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out1_l << avg << endl;
}
void Prim( int v ) {

        for( int i=0; i<v; ++i )
                for( int j=i+1; j<v; ++j )
                        if( matrix[ i ][ j ] != 0 ) {
                                graf_m->AddUndirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                                graf_l->AddUndirectEdge( i + 1, j + 1, matrix[ i ][ j ] );
                        }

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_m->Prim(1);
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out2_m << avg << endl;

        sum = 0.0;

        for( int i=0; i<iIle; ++i ) {

                tstart = clock();
                graf_l->Prim(1);
                tstop = clock();
                ttime = (double)(tstop-tstart)/CLOCKS_PER_SEC;
                sum += ttime;
        }

        avg = sum / dIle;
        out2_l << avg << endl;
}

int main( int argc, char ** argv ) {

        char t_alg[4] = { 'd', 'b', 'k', 'p' };
        int v[] = { 10, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000 };
        int e;

        if( argc < 3 ) {

                help();

                return 1;
        }

        int alg = atoi(argv[1]);
        int nr = atoi(argv[2]);
        string s1_m, s1_l, s2_m, s2_l;

        sprintf((char*)s1_m.c_str(), "%c_m_%d.txt", t_alg[(alg-1)*2], nr);
        sprintf((char*)s1_l.c_str(), "%c_l_%d.txt", t_alg[(alg-1)*2], nr);
        sprintf((char*)s2_m.c_str(), "%c_m_%d.txt", t_alg[(alg-1)*2+1], nr);
        sprintf((char*)s2_l.c_str(), "%c_l_%d.txt", t_alg[(alg-1)*2+1], nr);

        out1_m.open(s1_m.c_str(), ios::out | ios::trunc);
        out1_l.open(s1_l.c_str(), ios::out | ios::trunc);
        out2_m.open(s2_m.c_str(), ios::out | ios::trunc);
        out2_l.open(s2_l.c_str(), ios::out | ios::trunc);

        if (!out1_m.is_open() || !out1_l.is_open() || !out2_m.is_open() || !out2_l.is_open()) {

                cout << "Uppsss, pliki nie otwarte;(";


                return 2;
        }

        int gestosc[] = { 2, 5, 10, 15, 20 };

        for( int ev=0; ev<5; ++ev ) {

                e = (double)v[nr]*(v[nr]-1)/2 / gestosc[ev];

                out1_m << e << "\t" << v[nr] << "\t";
                out1_l << e << "\t" << v[nr] << "\t";
                out2_m << e << "\t" << v[nr] << "\t";
                out2_l << e << "\t" << v[nr] << "\t";

                // tworzymy graf
                graf_m = new CGraph( v[nr], e, CGraph::Matrix );
                graf_l = new CGraph( v[nr], e, CGraph::Lists );

                switch( alg ) {

                        case 1:
                                matrix = graf_m->RandomMatrix( CGraph::Direct );
                                Dijkstra(v[nr]);
                                BellmanFord(v[nr]);
                                break;
                        case 2:
                                matrix = graf_m->RandomMatrix( CGraph::UnDirect );
                                Kruskal(v[nr]);
                                Prim(v[nr]);
                                break;
                        default:
                                help();
                                return 1;
                }

                // debug
                printf( "v:%d e:%d\n", v[nr], e );
        }

        out1_m.close();
        out1_l.close();
        out2_m.close();
        out2_l.close();


        /*
        // przy skierowanym grafie a -> b
        // przy nieskierowanym wiadomo
        //              wierzcholki a, b, waga
        int test[][3] = { { 1, 2, 3 },
                                          { 1, 4, 3 },
                                          { 2, 3, 2 },
                                          { 3, 1, 6 },
                                          { 3, 6, 1 },
                                          { 4, 5, 1 },
                                          { 5, 3, 1 },
                                          { 5, 6, 2 },
                                          { 6, 4, 3 } };
        int e = 9;
        int v = 6;


        CGraph * graf = new CGraph( v, e, CGraph::Matrix );

        for( int i=0; i<e; ++i ) {

                //graf->Add     // i teraz co tu damy? skierowane czy nie?
                // bo pewnie trzeba bedzie robic dla grafy
                // jeden dla moichalgorytmow(skierowany)
                // drugi dla twoich(nieskierowany)
                // klasa oczywi?cie ta sama ale dwie instancje.
                // ?

                graf->AddDirectEdge( test[i][0], test[i][1], test[i][2] );
        }

        int * d = graf->Dijkstra( 1 );

        for( int i=0; i<v; ++i ) {

                printf( "%d ", d[ i ] );
        } 
        */
        //////TEST1
        /*
        int test[][3] = { { 1, 2, 4 },
                                          { 2, 3, 2 },
                                          { 1, 3, 7 },
                                          { 1, 4, 3 },
                                          { 3, 5, 1 },
                                          { 4, 5, 3 },
                                          { 2, 6, 5 },
                                          { 5, 6, 1 },
        };
        int e=8, v=6;
        CGraph * graf = new CGraph( v, e, CGraph::Matrix);
        for( int i=0; i<e; ++i )
                graf->AddUndirectEdge( test[i][0], test[i][1], test[i][2] );
        graf->Kruskal();*/
        ///////TEST2
        /*int test2[][3] = { { 1, 2, 4 },
                                          { 1, 8, 8 },
                                          { 2, 8, 11 },
                                          { 2, 3, 8 },
                                          { 3, 9, 2 },
                                          { 8, 9, 7 },
                                          { 7, 9, 6 },
                                          { 7, 8, 1 },
                                          { 3, 4, 7 },
                                          { 3, 6, 4 },
                                          { 6, 7, 2 },
                                          { 4, 6, 14 },
                                          { 4, 5, 9 },
                                          { 5, 6, 10 },
        };
        int test3[][3] = { { 1, 2, 10 },
                                          { 1, 3, 5 },
                                          { 2, 4, 1 },
                                          { 2, 3, 2 },
                                          { 3, 5, 2 },
                                          { 3, 4, 9 },
                                          { 3, 2, 3 },
                                          { 4, 5, 4 },
                                          { 5, 4, 6 },
                                          { 5, 1, 7 }
        };
        int e2=14, v2=9;
        CGraph * graf2 = new CGraph( v2, e2, CGraph::Matrix);
        for( int i=0; i<e2; ++i )
                graf2->AddUndirectEdge( test2[i][0], test2[i][1], test2[i][2] );
        //graf2->Kruskal();

        //graf2->Prim(1);


        int e3 = 5000, v3 = 1000;
        CGraph * graf3 = new CGraph( v3, e3, CGraph::Matrix );
        CGraph * graf4 = new CGraph( v3, e3, CGraph::Lists );
        int ** matrix = graf3->RandomMatrix( CGraph::UnDirect );
        for( int i=0; i<v3; ++i )
                for( int j=i+1; j<v3; ++j )
                        if( matrix[ i ][ j ] != 0 )
                        {
                                graf3->AddUndirectEdge( i + 1, j + 1, matrix[ i ][ j ] ); //lista sasiedztwa
                                //graf4->AddUndirectEdge( i + 1, j + 1, matrix[ i ][ j ] ); //lista sasiedztwa
                        }
        int * d = graf3->Dijkstra( 1 );
        for( int i=0; i<v3; ++i ) {

                std::cout << d[ i ] << " ";
        }
        
        double tstart, tstop, ttime;
        tstart = (double)clock()/CLOCKS_PER_SEC;
        graf3->Kruskal();
        tstop = (double)clock()/CLOCKS_PER_SEC;
        ttime = tstop-tstart;
        std::cout << ttime*1000 << " ms";
        tstart = (double)clock()/CLOCKS_PER_SEC;
        graf3->Prim(1);
        tstop = (double)clock()/CLOCKS_PER_SEC;
        ttime = tstop-tstart;
        std::cout << ttime*1000 << " ms";*/






        //getch();
        return 0;
}